//Search Demo using linearSearch, BinarySearch and sorting
// By Ben 20:24 01/10/2018

#include <iostream>
using namespace std;

template<typename T>
void Sort(T *items, int count){
	int x = 0;
	int y = 0;
	T tmp;
	
	for (int x = 0; x < count; x++){
		for (int y = x + 1; y < count; y++){
			if (items[x] > items[y]){
				tmp = items[y];
				items[y] = items[x];
				items[x] = tmp;
			}
		}
	}
}

template<typename T>
int BinarySearch(T *items, int left, int right, T find){
	
	if (right >= left){
		int mid = left + (right - left) / 2;

		if (items[mid] == find){
			return mid;
		}
		else if(items[mid] > find){
			return BinarySearch(items, left, mid - 1, find);
		}
		else
		{
			return BinarySearch(items, mid + 1, right, find);
		}
	}

	return -1;
}

template<typename T>
int linearSearch(T *items, int size, T find){
	int idx = -1;
	//Search the array for find
	for (int i = 0; i < size; i++){
		if (items[i] == find){
			idx = i;
			break;
		}
	}
	return idx;
}

int main(){
	//Set random letters
	char Alpha[] = { 'g', 'c', 'h', 'f', 'd', 'e', 'b','a' };
	//Get the length of the array
	int nsize = sizeof(Alpha) / sizeof(char);

	std::cout << "Unsorted array: ";
	//Display unsorted array
	for (int i = 0; i < nsize; i++){
		std::cout << (char)Alpha[i];
	}
	std::cout << endl;
	//Locate the letter f in the array using linearSearch on un-sorted array
	std::cout << "f was found at index: " << linearSearch<char>(Alpha, nsize, 'f') << endl;
	std::cout << endl;
	std::cout << "Sorted array: ";
	//Sort the random letters in the array.
	Sort<char>(Alpha, nsize);

	for (int i = 0; i < nsize; i++){
		std::cout << (char)Alpha[i];
	}
	std::cout << endl;

	//Locate the letter f in the array using BinarySearch on sorted array
	std::cout << "f was found at index: " << BinarySearch<char>(Alpha,0, nsize, 'f') << endl;

	return 0;
}